package 笔试.拼多多;

import java.util.HashSet;
import java.util.Set;

/**
 * 拿到一堆数字进行任意排列并组成一个乘法算式，求最后乘出的结果最大
 */
public class PinDuoDuoDemo04 {
    static boolean flag[] = new boolean[10];
    static int test[] = new int[10];
    static int max = -1;

    public static void main(String[] args) {
        dfs(1);
        System.out.println(""+max);

    }

    static void dfs(int step) {

        if(step>9) {
            check();
            return;
        }
        for(int i = 1;i<=9;i++) {
            if( flag[i]==false ) {  //没有被访问过
                flag[i] = true;
                test[step] = i;
                dfs(step+1);
                flag[i]=false;
            }
        }
    }

    static void check() {
        for(int i =2;i<=9;i++) {
            //将10个数字 分成两部分  两部分都是数字
            int a,b;
            a = transfer(1, i);
            b = transfer(i,10);



            int tempMax,tempNum;
            tempMax = a*b;
            tempNum = tempMax;

            //使用hashset来判断乘积是否存在重复的值
            Set<Integer> numSet = new HashSet<>();
            boolean flag = false;
            while(tempMax!=0) {
                if((tempMax%10)==0) {   //不应该存在可以整除10的
                    flag = true;
                    return;
                }
                numSet.add(tempMax%10);
                tempMax = tempMax / 10;
            }
            //9个不重复数 最大乘积和原来的比较
            if(numSet.size()==9 && tempNum>max && !flag) {
                System.out.println(a+"*"+b);
                max = tempNum;
            }
        }
    }

    static Integer transfer(int start,int end) {
        String str = new String();
        for(int i = end-1;i>=start;i--) {
            str = str+test[i];
        }
        return Integer.parseInt(str);
    }


}
